package com.genius.Genius.Polymer.Tree.BPtree;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

public class BPlusTree<T> {
    private final static int DEFAULT_DEGREE = 4;
    private int degree;
    private AtomicInteger size;
    private BPlusNode root = new BPlusNode(0,null,null,true);
    private BitSet keySet = new BitSet();

    public BPlusTree(int degree) {
        if(degree < 2){
            throw new RuntimeException("degree must > 0!");
        }
        this.degree = degree;
        this.size = new AtomicInteger(0);
    }

    public  BPlusTree(){
        this.degree = DEFAULT_DEGREE;
        this.size = new AtomicInteger(0);
    }

    public T searchByKey(int key){
        BPlusNode currentNode = root;
        boolean bInsert = false;
        while(true){
            int searchIndex = currentNode.search(key);
            if(searchIndex<0){
                searchIndex = currentNode.rawInsertIndex(searchIndex);
                bInsert = true;
            }
            if(currentNode.isLeaf){
                return bInsert?null:currentNode.getLeafValue(searchIndex);
            }else{
                currentNode = currentNode.getNoLeafNode(searchIndex);
            }
            bInsert = false;
        }
    }


    private BPlusNode searchTheNode(BPlusNode node,int key){
        BPlusNode currentNode = node;
        while(true){
            int searchIndex = currentNode.search(key);
            if(searchIndex<0){
                searchIndex = currentNode.rawInsertIndex(searchIndex);
            }
            if(currentNode.isLeaf){
                return currentNode;
            }else{
                currentNode = currentNode.getNoLeafNode(searchIndex);
            }
        }
    }

    //TODO 需要优化
    public List<T> searchByKeys(int...keys){
        List<T> res = new ArrayList<>();
        for (int key : keys) {
            res.add(searchByKey(key));
        }
        return res;
    }

    public List<T> searchByCondition(int keys,int gt,int lt){
       return null;
    }

    public int hashKey(T value){
        return value.hashCode();
    }

    public boolean insert(int key,T value){
        if(this.isExist(key)){
            update(key,value);
            return false;
        }
        BPlusNode newNode = new BPlusNode(key,value,null,true);
        return insert(newNode);
    }

    private boolean insert(BPlusNode newNode){
        BPlusNode test = root;
        BPlusNode currentNode = searchTheNode(root, newNode.key);
        boolean bNeedSplit = currentNode.insert(newNode,newNode.key);

        if(bNeedSplit){
            boolean split = split(currentNode);
        }
        keySet.set(newNode.key);
        size.incrementAndGet();
        return true;
    }

    public boolean insert(T value){
        return insert(hashKey(value),value);
    }

    public boolean update(int key,T value){
        return false;
    }

    public boolean delete(int key){
        return false;
    }

    private boolean split(BPlusNode node){
        int mid = degree/2;
        BPlusNode midNode = node.keyList.get(mid);

        BPlusNode splitNode = new BPlusNode(0,null,null,node.isLeaf);
        BPlusNode nodeParent = node.parentNode == null?createNonLeafNode(null):node.parentNode;

        splitNode.parentNode = node.parentNode = nodeParent;

        LinkedList<BPlusNode> tempList = node.keyList;

        node.key = midNode.key;
        splitNode.key = tempList.getLast().key;
        //set Leaf Node keyList
        splitNode.keyList = new LinkedList<>(tempList.subList(mid+1,tempList.size()));
        node.keyList = new LinkedList<>(tempList.subList(0,mid+1));

        if(nodeParent.isEmpty()){
            root = nodeParent;
            nodeParent.keyList.add(node);
            nodeParent.keyList.add(splitNode);
            return true;
        }

        if (node.parentNode.insert(splitNode,splitNode.key)) {
            return split(node.parentNode);
        }

        return true;
    }

    public boolean isExist(int key){
        return keySet.get(key);
    }

    public BPlusNode createLeafNode(int key,T value,BPlusNode parent){
        return new BPlusNode(key,value,parent,true);
    }

    public BPlusNode createNonLeafNode(BPlusNode parent){
        return new BPlusNode(0,null,parent,false);
    }

    class BPlusNode{
        private int key;
        private T value;

        private LinkedList<BPlusNode> keyList = new LinkedList<>();
        private BPlusNode parentNode;

        private boolean isLeaf;

        public BPlusNode(int key, T value, LinkedList<BPlusNode> keyList, BPlusNode parentNode, boolean isLeaf) {
            this.key = key;
            this.value = value;
            this.keyList = keyList;
            this.parentNode = parentNode;
            this.isLeaf = isLeaf;
        }

        public BPlusNode(int key, T value, BPlusNode parentNode, boolean isLeaf) {
            this.key = key;
            this.value = value;
            this.parentNode = parentNode;
            this.isLeaf = isLeaf;
        }

        public BPlusNode(int key,T value){
            this.key = key;
            this.value = value;
        }

        private Comparator<BPlusNode> getComparator(){
            return (node1,node2)->{
                if(node1.key == node2.key){
                    return 0;
                }
                return node1.key - node2.key;
            };
        }

        private int search(int key){
            return Collections.binarySearch(keyList, new BPlusNode(key,null), getComparator());
        }

        /**
         * Insert and check if separation is required
         * @param newNode
         * @return
         */
        private boolean insert(BPlusNode newNode,int index){
            newNode.parentNode = this;
            int search = this.search(index);
            search = search<0?parseInsertIndex(search):search;
            keyList.add(search,newNode);
            return isUpOver();
        }

        private boolean delete(int deleteIndex){
            if (keyList.remove(deleteIndex) == null) {
                throw new RuntimeException("delete error!");
            }
            return isDownOver();
        }

        private int parseInsertIndex(int index){
            return -1*index-1;
        }

        private int rawInsertIndex(int insertIndex){
            insertIndex = parseInsertIndex(insertIndex);
            return isOutOfCurrentKeyList(insertIndex)?keyList.size()-1:insertIndex;
        }

        private boolean isOutOfCurrentKeyList(int index){
            return index >= keyList.size();
        }

        private T getLeafValue(int key){
            BPlusNode bPlusNode = this.keyList.get(key);
            return bPlusNode==null?null:bPlusNode.value;
        }

        private BPlusNode getNoLeafNode(int key){
           return this.keyList.get(key);
        }

        private boolean isUpOver(){
            return keyList.size() > degree;
        }

        private boolean isDownOver(){
            return keyList.size() <= degree/2;
        }

        private boolean isEmpty(){
            return this.keyList.isEmpty();
        }
    }
}
